home *** CD-ROM | disk | FTP | other *** search
/ HPAVC / HPAVC CD-ROM.iso / VELENG10.ZIP / BINTREE.C < prev    next >
C/C++ Source or Header  |  1997-07-27  |  4KB  |  189 lines
  1. // ****************************************************************************
  2. // *                                                                          *
  3. // *                      Velena Source Code V1.0                             *
  4. // *                   Written by Giuliano Bertoletti                         *
  5. // *       Based on the knowledged approach of Louis Victor Allis             *
  6. // *   Copyright (C) 1996-97 by Giuliano Bertoletti & GBE 32241 Software PR   *
  7. // *                                                                          *
  8. // ****************************************************************************
  9.  
  10. // Portable engine version.
  11. // read the README file for further informations.
  12.  
  13. // ==========================================================================
  14.  
  15. #include <stdio.h>
  16. #include <string.h>
  17. #include <stdlib.h>
  18. #include <malloc.h>
  19.  
  20. #include "connect4.h"
  21. #include "con4vals.h"
  22. #include "rules.h"
  23. #include "pnsearch.h"
  24. #include "proto.h"
  25.  
  26. #define MAXNODECHECK 2810L
  27.  
  28. struct bintree *tree_pool;
  29. short tpp,semaphore;
  30.  
  31. short bin_compare(unsigned char *c1,unsigned char *c2)
  32.     {
  33.     unsigned long *p1,*p2;
  34.     short flag=0,x;
  35.  
  36.     p1=(unsigned long *)c1;
  37.     p2=(unsigned long *)c2;
  38.  
  39.     for(x=0;x<12 && flag==0;x++)
  40.         {
  41.         if(p1[x]==p2[x]) continue;
  42.         else if(p1[x]>p2[x]) flag=-1;
  43.         else flag=1;
  44.         }
  45.  
  46.     return flag;
  47.     }
  48.  
  49. struct bintree *init_bin_tree(struct node *node)
  50.     {
  51.     struct bintree *root;
  52.  
  53.     root=(struct bintree *)malloc(sizeof(struct bintree));
  54.     if(!root) fatal_error("Cannot allocate root bintree");
  55.  
  56.     root->parent=NULL;
  57.     root->lson=NULL;
  58.     root->rson=NULL;
  59.     root->node=node;
  60.  
  61.     return root;
  62.     }
  63.  
  64. void free_bin_tree(struct bintree *tree)
  65.     {
  66.     if(!tree) return;
  67.     if(tree->lson) free_bin_tree(tree->lson);
  68.     if(tree->rson) free_bin_tree(tree->rson);
  69.     free(tree);
  70.     }
  71.  
  72. struct bintree *set_node(struct bintree *root,struct node *node,short depth)
  73.     {
  74.     struct bintree *child;
  75.  
  76.     child=(struct bintree *)malloc(sizeof(struct bintree));
  77.     if(!child) fatal_error("Out of memory, while building tree!");
  78.  
  79.     child->parent=root;
  80.     child->lson=NULL;
  81.     child->rson=NULL;
  82.     child->node=node;
  83.  
  84.     return child;
  85.     }
  86.  
  87. struct node *check_node(struct bintree *root,struct node *node,short depth)
  88.     {
  89.     short cmp;
  90.  
  91.     cmp=bin_compare(root->node->square,node->square);
  92.  
  93.     if(cmp<0)
  94.         {
  95.         if(!root->lson)
  96.             {
  97.             root->lson=set_node(root,node,depth);
  98.             return NULL;
  99.             }
  100.         else return check_node(root->lson,node,depth+1);
  101.         }
  102.     else if(cmp>0)
  103.         {
  104.         if(!root->rson)
  105.             {
  106.             root->rson=set_node(root,node,depth);
  107.             return NULL;
  108.             }
  109.         else return check_node(root->rson,node,depth+1);
  110.         }
  111.  
  112.     return root->node;
  113.     }
  114.  
  115. /* ========================= Faster Version ============================ */
  116.  
  117. struct bintree *fast_init_bin_tree(struct node *node)
  118.     {
  119.     struct bintree *root;
  120.  
  121.     if(semaphore==1) fatal_error("Recursive calls forbidden");
  122.     semaphore=1;
  123.     tpp=1;
  124.  
  125.     tree_pool=root=(struct bintree *)malloc(MAXNODECHECK*sizeof(struct bintree));
  126.     if(!root) fatal_error("Cannot allocate root bintree");
  127.  
  128.     root->parent=NULL;
  129.     root->lson=NULL;
  130.     root->rson=NULL;
  131.     root->node=node;
  132.  
  133.     return root;
  134.     }
  135.  
  136. void fast_free_bin_tree(struct bintree *tree)
  137.     {
  138.     if(!semaphore || tree!=tree_pool) fatal_error("Free bintree error");
  139.     semaphore=0;
  140.     free(tree_pool);
  141.     tree_pool=NULL;
  142.     }
  143.  
  144. struct bintree *fast_set_node(struct bintree *root,struct node *node,short depth)
  145.     {
  146.     struct bintree *child;
  147.  
  148.     child=(struct bintree *)&tree_pool[tpp++];
  149.     if(tpp>=MAXNODECHECK)
  150.         {
  151.         printf("TPP=%d\n",tpp);
  152.         fatal_error("Out of memory, while building tree!");
  153.         }
  154.     child->parent=root;
  155.     child->lson=NULL;
  156.     child->rson=NULL;
  157.     child->node=node;
  158.  
  159.     return child;
  160.     }
  161.  
  162. struct node *fast_check_node(struct bintree *root,struct node *node,short depth)
  163.     {
  164.     short cmp;
  165.  
  166.     cmp=bin_compare(root->node->square,node->square);
  167.  
  168.     if(cmp<0)
  169.         {
  170.         if(!root->lson)
  171.             {
  172.             root->lson=fast_set_node(root,node,depth);
  173.             return NULL;
  174.             }
  175.         else return fast_check_node(root->lson,node,depth+1);
  176.         }
  177.     else if(cmp>0)
  178.         {
  179.         if(!root->rson)
  180.             {
  181.             root->rson=fast_set_node(root,node,depth);
  182.             return NULL;
  183.             }
  184.         else return fast_check_node(root->rson,node,depth+1);
  185.         }
  186.  
  187.     return root->node;
  188.     }
  189.